1. Field of the Invention
The present invention relates to a template matching apparatus and method, and more particularly to a template matching apparatus and method which provides a judging function of judging whether an inspection object has the same pattern as that of a template and a position detecting function of detecting a position of the same pattern, and is suitable for utilizing various inspecting apparatus, recognizing apparatus, judging apparatus and the like in which these functions are built in.
2. Description of the Related Art
Techniques called template matching have been used widely. A template is created from an image photographed in advance or data acquired in advance, and a recognizing or judging function of judging whether an inspection object has the same pattern as that of a template or a position detecting function of detecting a position of the same pattern is created.
For example, a fundamental template matching method is described in “Basics and Applications of Digital Image Processing by Visual C#.NET & Visual Basic.NET—From Fundamental Concept to Portrait Image Recognition”, by Kouichi SAKAI, CQ Publication Co. Ltd, First Edition, Sep. 1, 2003, Chapter 5, Section 3, pp. 84 to 86. In FIGS. 5 and 6 of this document, (a) a portrait image of a girl is used as an original image, (b) the left eye area is cut as a template, an image obtained by density conversion of the original image is used as an input image, and the results of correlation calculations between each area of the input image and the template are illustratively shown. This document illustrates that (c) only the position of the left eye area cut as the template matches at a correlation coefficient threshold value of 0.99 or higher, and that (d) not only the position of the left eye area but also some candidate positions of the right eye match at a correlation coefficient threshold value of 0.8.
In “Basics and Applications of Digital Image Processing by Visual C#.NET & Visual Basic.NET—From Fundamental Concept to Portrait Image Recognition”, by Kouichi SAKAI, CQ Publication Co. Ltd, First Edition, Sep. 1, 2003, since the input image is an image obtained through proper density conversion of the original image, the position having the highest correlation coefficient is at the left eye. Although not described in this document, there is generally a case in which the position having the highest correlation coefficient is not always the position correctly detecting a desired position. For example, if an image of the original image added with a large density change or noises or a portrait image of another person is used as the input image, there is no guarantee that the position of the left eye is the position having the highest correlation coefficient, but there is a possibility that the position of the right eye is the position having the highest correlation coefficient. In such a case, if the position having the highest correlation coefficient is detected as the position of the left eye, a desired position cannot be detected but it is erroneously recognized.
With the above-described template matching techniques, if the detection position of an input image has a pattern deformed greatly from the template or a very similar pattern exists at another position, the position detection becomes erroneous.
Techniques of shortening a matching calculation time is described in JP-A-63-211474, JP-A-2001-351102, and “Basics and Applications of Digital Image Processing by Visual C#.NET & Visual Basic.NET—From Fundamental Concept to Portrait Image Recognition”, by Kouichi SAKAI, CQ Publication Co. Ltd, First Edition, Sep. 1, 2003. In JP-A-63-211474, the size, sampling rate and candidate area of the image of a template is reduced hierarchically so that high speed calculations are possible more than if a large size template not reduced hierarchically is used. In “Basics and Applications of Digital Image Processing by Visual C#.NET & Visual Basic.NET—From Fundamental Concept to Portrait Image Recognition”, by Kouichi SAKAI, CQ Publication Co. Ltd, First Edition, Sep. 1, 2003, it is described that if subtraction and normalization of average values of a binarized image can be omitted, a “distance” is used as an evaluation formula to shorten a calculation time and speed up processing. JP-A-2001-351102 describes that if a recognition object has a relatively simple shape, a circle having as its diameter a width of a circumscribed square of the recognition object is used as a template to speed up matching calculations of a binarized image.
JP-A-8-181053 describes a method of preventing erroneous recognition of position alignment suitable for an exposure system for large size liquid crystal displays. According to the techniques described in JP-A-8-181053, an area in a template image where it is known beforehand that many errors occur is masked, a corresponding candidate area of a photographed image (input image) is also masked, and only an area not masked is evaluated by calculations based on a predetermined evaluation formula. It is therefore possible to improve a position detection precision through evaluation excluding an area having a large error.
According to the above-described techniques, in order to suppress erroneous recognition of template matching, an area having a large error is masked to exclude evaluation, as described in JP-A-8-181053. This conventional approach is, however, associated with a problem that a predetermined partial area cannot be masked and erroneous recognition cannot be suppressed sufficiently, if an S/N ratio of a template and a photographed image (input image) is poor, and while matching results of each pixel are processed synthetically, errors are accumulated gradually on the whole image, if a structural portion in the photographed image (input image) is missed accidentally, or if a large error occurs accidentally in an unidentified area such as an area having an unnecessary bump.
Even if a large error occurs inevitably as described above, if it is guaranteed that a partial image similar to the template does not exist at the position other than the correct position in the input image, it is possible to detect a correct position. However, if an image similar to the template exists at another position other than the correct position in the input image, this image is erroneously recognized as another similar image.